/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:最大正方形.java
 * Date:2021/02/18 14:21:18
 */

package org.bytedance.动态和贪心;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 */
public class 最大正方形 {

    public static void main(String[] args) {
        最大正方形 instance = new 最大正方形();
        char[][] inputs = new char[][]{
                new char[]{'1', '0', '1', '0', '0'},
                new char[]{'1', '0', '1', '1', '1'},
                new char[]{'1', '1', '1', '1', '1'},
                new char[]{'1', '0', '0', '1', '0'}
        };
        int i = instance.maximalSquare(inputs);
        System.out.println(i);

        inputs = new char[][]{
                new char[]{'0', '1'},
                new char[]{'1', '0'}
        };
        i = instance.maximalSquare(inputs);
        System.out.println(i);
    }

    /**
     * 可以使用动态规划降低时间复杂度。我们用 \textit{dp}(i, j)dp(i,j) 表示以 (i, j)(i,j) 为右下角，且只包含 11 的正方形的边长最大值。
     * 如果我们能计算出所有 \textit{dp}(i, j)dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 11 的正方形的边长最大值，其平方即为最大正方形的面积。
     * <p>
     * 那么如何计算dp中每个元素的值呢？对于每个位置(i,j)，检查在矩阵中该位置的值
     * 如果该位置是0，那么dp(i,j)=0, 因为当前位置不可能在由1组成的正方形中。
     * 如果该位置是1， 则dp(i,j) 的值由其上方、左方、左上角三个相邻位置的dp值决定。
     * 所以状态转移方程是dp(i,j) = min(dp(i-1, j-1), dp(i,j-1), dp(i-1,j)) + 1
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }

        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }

}
